package mylib.dir;

/**
 * Created with IntelliJ IDEA.
 * User: 1
 * Date: 14.08.12
 * Time: 22:26
 * To change this template use File | Settings | File Templates.
 */
public class Dsu {
    private int[] rank;
    private int[] size;
    private int[] parent;

    public Dsu(int n) {
        rank = new int[n];
        size = new int[n];
        parent = new int[n];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public boolean join(int u, int v) {
        u = getParent(u);
        v = getParent(v);
        if (u == v)
            return false;
        if (rank[u] < rank[v]) {
            parent[u] = v;
            size[v] += size[u];
        } else {
            parent[v] = u;
            size[u] += size[v];
            if (rank[u] == rank[v])
                ++rank[v];
        }
        return true;
    }

    public int getSize(int p) {
        return size[getParent(p)];
    }

    public int getParent(int p) {
        return parent[p] == p ? p : (parent[p] = getParent(parent[p]));
    }
}
